In recent years, many counterfeit products have been seen against genuine products such as printer cartridges, battery cells and cartridges for video games. Counterfeit products have the same functions as genuine products, by using results of an internal structure analysis of the genuine products, an analysis of IC chips existing in the genuine products, and the like. There are many cases among these counterfeited products of infringement of rights of the genuine manufacturers that manufacture the genuine products, and there is a strong demand for a counterfeit-countermeasure technique.
As a preventive method for counterfeit products described above, an authentication function has been given to genuine products. One of effective measured to realize the authentication function is PUF (Physically Unclonable Function) in which a PUF circuit is embedded into a product that needs a countermeasure against counterfeit products.
The PUF is a function that returns a different output to respective devices on which the PUF is implemented. However, there is no need to individually set a function that outputs a different value for respective devices, and the same circuit realizes the function. That is, the PUF circuit makes its output for respective devices totally different, by using a slight difference in physical characteristics in the devices such as signal delay and device characteristics. Therefore, this output becomes a value that is unique to the device (referred to as “individual-specific information”).
An ideal PUF circuit, once implemented on a device, outputs the same individual-specific information constantly for the device (Reliability), while PUFs implemented on different devices output totally different individual-specific information (Uniqueness). The output information of the PUF in devices described above may be compared to biological information such as the “fingerprint” for human. The fingerprint has the same characteristics as the output information of an ideal PUF, being unchanged for the same person with ages (Reliability), and on the other hand, while being totally different among different people (Uniqueness).
In addition, when PUF circuits of the same circuit configuration have the ideal reliability and uniqueness described above, even if the attacker breaks down the circuit and analyzes inside, it is impossible to generate a counterfeit chip.
The PUF is also used for the generation of identification information (ID) and the generation of a cryptographic key.
In many electronic device products, an individually unique ID is required. Conventionally, in many cases, a process to write in a different value for respective devices has been executed at the production stage. By using the PUF for the generation of the ID, the cost for this write-in process may be reduced.
In addition, for products including a cryptographic function, the use of the PUF improves the safety. A specific example is a smartcard in which an integrated circuit for information recording is embedded into a card. In addition, to ensure the confidentiality of communication, a cryptographic function is essential for SIM (Subscriber Identification Module) cards used for mobile phones and terminals for wireless Internet connection. By generating random numbers used for the generation of the cryptographic keys used for the encryption in these devices, the risk of the cryptographic key being analyzed by an attacker decreases significantly, improving the safety.
As the basic circuit configuration of the PUF, the Arbiter PUF and the Latch type PUF are explained first.
Meanwhile, in the following explanation herein, the high-level of the binary logic level with different potentials is expressed as the value “1”, and the low level is expressed as the value “0”.
First, the Arbiter PUF is explained. FIG. 1 is an illustration of the circuit configuration of the Arbiter PUF.
The Arbiter PUF 10 is configured including a total of 2n units of two-input/one-output selectors 11-0a, 11-0b, 11-1a, 11-1b, 11-2a, 11-2b, . . . , 11-(n−1)a and 11-(n−1)b, and a D-type flip-flop circuit 12.
Meanwhile, in the following explanation, when there is no particular need to distinguish, the, selector 11-0a, 11-0b, 11-1a, 11-1b, 11-2a, 11-2b, . . . , 11-(n−1)a and 11-(n−1)b are collectively referred to as the “selectors 11”.
To the first input terminal of the selector 11-1a and 11-1b, the output terminal of the selector 11-0a is connected, and to their second input terminal, the output terminal of the selector 11-0b is connected. In addition, to the first input terminal of the selector 11-2a and 11-2b, the output terminal of the selector 11-1a is connected, and to their second input terminal, the output terminal of the selector 11-1b is connected. A similar connection is performed for the rest of the selectors 11.
Meanwhile, to the selectors 11, a value cha[n−1:0] is input. This cha[n−1:0] is referred to as “challenge”, which is for giving a selection instruction to the selectors 11 as to output the signal input to which of the two input terminals of the selectors 11 to the output terminal.
In the configuration in FIG. 1, for example, to both of the selector 11-1a and 11-1b, cha[1] is input. The selector 11-1a is supposed to perform an operation to output the signal input to the first input terminal to the output terminal when cha[1]=1, and to output the signal input to the second input terminal to the output terminal when cha[1]=0. On the other hand, the selector 11-1b is supposed to perform an operation to output the signal input to the second input terminal to the output terminal when cha[1]=1, and to output the signal input to the first input terminal to the output terminal when cha[1]=0. Meanwhile, the other selectors 11 are also supposed to perform a similar operation.
In the Arbiter PUF 10, the D-type flip flop circuit 12 is referred to as the “Arbiter”. To the data input terminal D of the D-type flip flop circuit 12, the output terminal of the selector 11-(n−1)a is connected, and to its clock input terminal CLK, the output terminal of the selector 11-(n−1)b is connected. The output of the D-type flip flop circuit 12 becomes the output R of the Arbiter PUF 10. Meanwhile, the D-type flip flop circuit 12 is reset with initialization and its output becomes 0.
As described above, the Arbiter PUF 10 has a symmetrical configuration in which every n units of a total of 2n units of selectors 11 are connected in series to the D-type flip flop circuit 12. In addition, it is also preferable to make the wiring lengths of the connection between the selectors 11 and the connection between the selector 11-(n−1)a and 11-(n−1)b and the D-type flip flop circuit 12 as much as possible, to maintain the symmetry.
The Arbiter PUF 10 is a circuit that realizes the PUF using circuit delay.
To the Arbiter PUF 10, an edge signal that causes a state change in the D-type flip flop circuit 12 once input to the clock terminal of the D-type flip flop circuit 12 is input as an input signal. In this embodiment, the edge signal is assumed as a rising edge signal that changes the logic level from 0 to 1.
The rising edge signal input to the Arbiter PUF l-is input to the first input terminal and the second input terminal of the selectors 11-0a and 11-0b. Then, the edge signal goes through the selectors 11 in the route according to the value of the challenge cha[n−1:0] and reaches the data input terminal D and the clock input signal CLK of the D-type flip flop circuit 12 being the arbiter.
The output of the D-type flip flop circuit 12 is decided by the change point from 0 to 1 of the rising edge signal reached first to which of the data input terminal D and the clock input terminal CLK, and the output becomes the output of the Arbiter PUF 10 That is, when the change point reaches the clock input terminal CLK first, the output R of the Arbiter PUF becomes 0, and when the change point reaches the data input terminal D first, the output R of the Arbiter PUF 10 becomes 1.
As descried earlier, the Arbiter PUF 10 has a symmetrical configuration in which every n units of a total of 2n units of selectors 11 are connected in series. In addition, as described earlier, the wiring lengths between the respective elements are configured to be approximately equal. Therefore, in the circuit logic, the arrival of the rising edge signal at the data input terminal D and the clock input terminal CLK is at the same time, and the rising edge signals arriving at the two are supposed to be in the same phase. However, actually, there are cases in which the arrival of the rising edge signals at the two are not at the same time due to gate delay and line delay caused by the implementation conditions on the electronic device. The degree of the uniqueness in the arrival time is specific to the electronic device, while different for each device. That is, the degree of the uniqueness in the arrival time has the reliability and uniqueness that are the characteristics of the PUF described earlier, and may be used as the individual-specific information of the electronic device on which the Arbiter PUF 10 is implemented.
As described above, the Arbiter PUF 10 in FIG. 1 is configured to input the edge signal that causes a state change in the D-type flip flop circuit 12 to its clock terminal and also to input the edge signal logically in the same phase as the edge signal to its data input terminal. Then, the configuration is made so that the signal output from the output terminal of the D-type flip flop circuit 12 becomes the output of the Arbiter PUF 10.
In addition, as described above, the Arbiter PUF 10 is able to change the route in which the rising edge signal goes through the selector 11 by the value of the challenge Cha[n−1:0]. Therefore, when the value of the challenge Cha[n−1:0] is changed, a different value of output R is obtained. This output is referred to as a “response”.
Then, the relationship between the challenge Cha[n−1:0] and the response R in the Arbiter PUF 10 implemented on a specific device is studied in advance and recorded. By doing so, by studying the relationship of the challenge Cha[n−1:0] and the response R of the Arbiter PUF 10 of a device being the check target and checking it against the recorded content above, authentication may be performed as to whether the check target device is the specific device.
Next, the Latch-type PUF is explained. The Latch-type PUF realizes the PUF using metastable of the RS latch circuit.
First, metastable is explained using FIG. 2A and FIG. 2B.
FIG. 2A illustrates a circuit configuration example of the RS latch circuit. The RS latch circuit is constituted using NAND (negative AND) circuits 21 and 22.
The input of the RS latch circuit is negative logic. Meanwhile, in the drawing, the negative logic signal is expressed by adding an overbar on the signal name, while the negative logic signal is described herein as “#”. Therefore, for example, set input of the RS latch circuit in FIG. 2A is described as “#S”, and reset input is described as “#R”.
To the two inputs of the NAND circuits 21, respectively, the set input “#S” and the output of the NAND circuit 22 are input. Meanwhile, to the two inputs of the NAND circuit 22, respectively, the reset input “#R” and the output of the NAND circuit 21 are input. In addition, the output of the NAND circuit 21 becomes the output Q of the RS latch circuit. Meanwhile, from the output of the NAND circuit 22, output “#Q” is output.
FIG. 2B is the truth table of the RS latch circuit of FIG. 2A. Meanwhile, in the truth table, the set input S and the reset input R are described in positive logic.
As is understood from the truth table, in the RS latch circuit in FIG. 2A, the output value is maintained as it is and Q=Q, and “#Q”=“#Q” when the input S=0 and the input R=0. In addition, in the RS latch circuit, the output value is reset and, Q=0, and “#Q”=1 when the input S=0 and the input R=1. Furthermore, in the RS latch circuit, the output value is set and Q=1, “#Q”=0 when the input S=1 and the input R=0.
The logic of the output of the RS latch circuit in FIG. 2A is stable with any one of the combinations above. However, in the RS latch circuit, Q=“#Q”=1 when with input S=1 and input R=1. That is, in this case, the logic value of Q and the logic value of “#Q” that are supposed to indicate reverse logic become both “1”. At this time, the outputs of the RS latch circuit are both in the unstable state of the midpoint potential. Such an unstable state that is abnormal as a digital circuit is called metastable. Generally, in order to avoid such a state of metastable, input of S=1 and R=1 to the RS latch circuit is prohibited.
Next, the latch-type PUF using metastable of the RS latch circuit as described above is explained. FIG. 3 is a circuit configuration example of the latch-type PUF.
The latch-type PUF 20 is configured so that the same value A is input to both the set input “#S” and reset input “#R” of the RS latch circuit in FIG. 2A. There, the output Q and the output “#Q” of the RS latch circuit being the output of the PUF are assumed as B and C, respectively. That is, the latch-type PUF 20 is a circuit configured so that inputs are given to the RS latch circuit to make it enter the metastable state, and the signals output from the output terminal of the RS latch circuit become the output of the latch-type PUF 20.
In the latch-type PUF 20, when the input A=0, the output B and the output C both become 1, and the value of the output is stable in this state. However, here, when the value A is changed from 0 to 1, a state in which the output B is 1 and the output C is 0, and a state in which the output B is 0 and the output C is 1 are generated, making the output unstable. This is because the RS latch circuit is put in the metastable state, and its output is in the uncertain state. The latch-type PUF 20 is a PUF that utilizes this uncertainty.
The output of the latch-type PUF 20 takes one of the two values (0 and 1). However, when the latch-type PUF 20 is implemented on the device, three modes including one that always outputs 0, one that always outputs 1, one whose output is 0 or 1 and not fixed, that is, one that inputs a random number are obtained, and this modes of the output has reliability. Then, a plurality of the latch-type PUF 20 may be implemented on a device, and the outputs obtained may be used as individual-specific information about the device on which the latch-type PUF 20 is implemented.
Next, FIG. 4 is explained. FIG. 4 is an illustration of the individual-specific information generation apparatus being the background art.
The individual-specific information generation apparatus 30 is configured by implementing a plurality (n units) of the latch-type PUF 20 illustrated in FIG. 3 on a device 1 being an electronic device.
In the individual-specific information generation apparatus 30, choosing one of the n units of the latch-type PUFs 20 corresponds to the challenge described earlier. FIG. 4 represents a condition in which, by the challenge, 6 units of latch-type PUFs 20 from “latch 0” through “latch 5” are selected. The respective outputs RES[5:0] of the 6 units of latch-type PUFs 20 takes binary values (0 or 1), and these values are arranged to form a 6-bit bit string. The bit string becomes the response (characteristic value) described earlier, and may be used as individual-specific information of the device 1. Meanwhile, the number of pattern of individual-specific information that the individual-specific information generation apparatus 30 is, 2 to the sixth power patterns since a total of 6 latch-type PUF 20 are selected, that is, 64 patterns.
However, as described above, the latch-type PUF may output a random number. FIG. 4 represents a case in which the “latch 2” and the “latch 3” among the total of 6 units of the latch-type PUFs 20 output a random number. When the latch-type PUF 20 that outputs a random number is included in the selection by the challenge, the response that is supposed to be unchanged in the device 1 may become a different value, eliminating the reliability and making the use as a PUF impossible.
In this regard, a technique in which the individual-specific information generation apparatus 30 is equipped with a code error correction circuit has been known. In this technique, the configuration is made so that a bit string composed by arranging outputs of latch-type PUF 20 selected by the challenge are input to the code error correction circuit, and its output becomes the response of the individual-specific information generation apparatus 30. That is, the random number included in the bit string generated as described above from the latch-type PUF 20 is corrected by the code error correction circuit, so that the same response is constantly obtained for the same challenge in the device 1. In this technique, as described above, the reliability of the output of the individual-specific information generation apparatus 30 is maintained.
Meanwhile, it is also possible configure, in the individual-specific information generation apparatus 30 in FIG. 4, replacing the latch-type PUF 20 with the Arbiter PUF 10 in FIG. 1.
While the output of the Arbiter PUF 10 also takes one of the two values (0 and 1), when the different of the arrival times of the rising edge signals to the data input terminal D and the clock input terminal CLK is extremely small, the output may become a random number. That is, in a similar manner to the latch-type PUF 20, the Arbiter PUF 10 is also a digital circuit that individually outputs an output value being a prescribed output value (0 or 1) or a random number without the output with respect to a certain input being unambiguously determined. Therefore, the correction by the code error correction circuit on the bit string generated from the output of the Arbiter PUF 10 has an effect to maintain the reliability.
As other background techniques, several techniques to generate a random value using the uniqueness in physical characteristics of electronic devices. One of them is a technique to generate a random number in which a digital output value that is not unambiguously determined with respect to a digital input value and to equalize the frequencies of occurrence of “0” and “1” in the digital output value.    Patent Document 1: U.S. Pat. No. 3,604,674    Non-patent Document 1: Jae W. Lee and 5 others, “A technique to build a secret key in integrated circuits with identification and authentication applications”. IEEE VLSI Circuits Symposium. June 2004.    Non-patent document 2: Sandeep S. Kumar and 4 others, “Extend Abstract: The Butterfly PUF: Protecting IP on every FPGA”. IEEE International Workshop on Hardware-Oriented Security and Trust—HOST, 2008.    Non-patent Document 3: G. Edward. Suh and another, “Physical Unclonable Functions for Device Authentication and Secret Key Generation”. Design Automation Conference, June 2007.